#include <vector>
// 逐个元素依次旋转
using namespace std;
void rotate(vector<vector<int>> &matrix) {
  int n = matrix.size();
  if (n < 2) {
    return;
  }
  int start_row = 0, end_row = n - 1, start_col = 0, end_col = n - 1;
  while (end_row > start_row && end_col > start_col) {
    // 从坐上角偏移量为0的位置开始旋转 直到右上角元素之前为止 共n-1个元素
    for (int i = 0; i < end_row - start_row; i++) {
      //[0,0]->[0,n]
      int t1 = matrix[start_row + i][end_col];
      matrix[start_row + i][end_col] = matrix[start_row][start_col + i];
      //[0,n]->[n,n]
      int t2 = matrix[end_row][end_col - i];
      matrix[end_row][end_col - i] = t1;
      //[n,n]->[n,0]
      t1 = matrix[end_row - i][start_col];
      matrix[end_row - i][start_col] = t2;
      //[n,0]->[0,0]
      matrix[start_row][start_col + i] = t1;
    }
    start_row++;
    end_row--;
    start_col++;
    end_col--;
  }
}

int main() {
  vector<vector<int>> matrix{
      {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}};
  rotate(matrix);
  return 0;
}